package com.zxy.javaarithmetic.chapter_2_LinkList;

import java.util.Stack;

/*
 *  @项目名：  study
 *  @包名：    com.zxy.javaarithmetic.chapter_2_LinkList
 *  @文件名:   P_7_Palindrome
 *  @创建者:   zhangxy
 *  @创建时间:  2018/12/11 14:35
 *  @描述：    判断链表是否是回文结构
 */
public class P_7_Palindrome {

	public static void main(String[] args) {
		Node head = new Node(1);
		head.next = new Node(2);
		head.next.next = new Node(2);
		head.next.next.next = new Node(1);

		System.out.println("isPalindrome=" + isPalindrome3(head));
		LinkListUtils.printRingNode(head);
	}

	/**
	 * 计算链表长度，将链表前半部分压栈。一次去除栈中数据和链表的相比较，判断是否为回文结构
	 * @param head
	 * @return
	 */
	private static boolean isPalindrome1(Node head) {
		if (head == null || head.next == null) {
			return true;
		}
		Stack<Node> stack = new Stack<>();
		int n = 0;
		Node node = head;
		while (node != null) {
			n++;
			node = node.next;
		}
		int half = n / 2;
		for (int i = 0; i < half; i++) {
			stack.push(head);
			head = head.next;
		}
		if (n % 2 != 0) {
			head = head.next;
		}
		while (!stack.isEmpty()) {
			if (stack.pop().value != head.value) {
				return false;
			}
			head = head.next;
		}
		return true;
	}

	/**
	 * 计算链表中点，将中点之后的数据压栈，然后比较
	 * @param head
	 * @return
	 */
	private static boolean isPalindrome2(Node head) {
		if (head == null || head.next == null) {
			return true;
		}
		//right为中点之后的第一个节点
		Node right = head.next;
		Node cur = head;
		while (cur.next != null && cur.next.next != null) {
			right = right.next;
			cur = cur.next.next;
		}
		Stack<Node> stack = new Stack<>();
		while (right != null) {
			stack.push(right);
			right = right.next;
		}
		while (!stack.isEmpty()) {
			if (stack.pop().value != head.value) {
				return false;
			}
			head = head.next;
		}
		return true;
	}

	//时间复杂度O(n),空间复杂度O(1)
	private static boolean isPalindrome3(Node head){
		if (head == null || head.next == null) {
			return true;
		}
		boolean result = true;

		//找中间节点
		Node right = head;
		Node cur = head;
		while (cur.next != null && cur.next.next != null) {
			right = right.next;
			cur = cur.next.next;
		}

		//反转后半部分链表
		cur = right.next;
		right.next = null;
		Node pre = right;
		Node node1 = null;
		while (cur != null){
			node1 = cur.next;
			cur.next = pre;
			pre = cur;
			cur = node1;
		}

		//判断是否为回文结构
		cur = head;
		right = pre;
		while (cur != null && right != null){
			if(cur.value != right.value){
				result =  false;
				break;
			}
			cur = cur.next;
			right = right.next;
		}

		//恢复链表结构
		cur = pre.next;
		pre.next = null;
		while (cur != null){
			node1 = cur.next;
			cur.next = pre;
			pre = cur;
			cur = node1;
		}

		return result;
	}
}
